The present invention relates to a circuit which can perform a multiplication remainder calculation in a Montgomery space at a high speed.
In recent years, the necessity of performing individual authentication has been increased with spread of IC cards, portable terminals and others. In, e.g., a portable terminal used for online shopping, this authentication must be executed within a short time so as not to keep a customer waiting. In such an authentication and others, data is usually encrypted in order to protect personal information. In RSA cryptography or elliptic curve cryptography, which is often used for such encryption, n-bit multiplication remainder calculation is a bottleneck. Thus, the multiplication remainder calculation must be performed at a high speed.
In the simple multiplication remainder calculation, n-bit register is required when it calculate a product of two n-bit values and division is necessary, e.g., 1024 bits is adopted, 2048-bit register is required, and division based on the 1024-bit data is necessary. However, the load of the calculation relative to the division is high, which makes it difficult to perform encryption processing in the short time.
A Montgomery (Peter L. Montgomery) method is famous as a method enabling the multiplication remainder calculation without using the division in the multiplication remainder calculation. In the Montgomery method, calculating a remainder of a product of two numeric values A and B based on a modulus N can be expressed as follows:A*B (mod N)  (Expression 1)
Meanwhile, consideration is given as to a remainder space (which will be referred to as a Montgomery space hereinafter) of the modulus N using a large numeric value R as the remainder space when the numeric value R forms a prime number with the modulus N (gcd(N, R)=1). The numeric values A and B in Expression 1 are dealt as A′=AR(modN) and B′=BR(modN) in the Montgomery space. Further, a product Mont(A′·B′) in the Montgomery space is defined by the following expression:Mont(A′·B′)=A′*B′*R^−1 (mod N)  (Expression 2)Where R^−1 is an inverse number in the modulus N of the R. A result obtained from Expression 2 is of course a value in the Montgomery space, and hence the following expression can be obtained as different from Expression 1.A*B*R (mod N)  (Expression 3)Thus, after obtaining the multiplication remainder in the Montgomery space, the post-processing of multiplying R^−1 is usually required.
Here, encrypting a message M will be considered on the presumption of RSA cryptography. The message M is a large numeric value expressing a plain text by binary notation. Encryption is executed by exponential calculation of C=M^e (modN). This calculation can be readily executed by repeating the multiplication remainder calculation in the Montgomery space.T1=R  (A1)T2=Mont(M,R^2)  (A2)for(j=0;j<k;j++){  (A3)if(ej==1)T1=Mont(T2,T1)  (A4)T2=Mont(T2,T2)}  (A5)C=Mont(T1,1)  (A6)The above table shows this multiplication remainder calculation. In the table, an expression A1 and an expression A2 are pre-processing in order to utilize the Montgomery space. Of these expressions, the expression A2 converts the message M into a numeric value M′ in the Montgomery space. That is, M′=M*R (modN). The FOR sentence in each of the expressions A3 to A5 calculates the e-th power (modn) of M′ in the Montgomery space. A result of this calculation is M′^e=M^e*R (modN), and post-processing of the expression A6 is required in order to obtain a final result C. It is to be noted that the expression A4 is a part which forms a cryptogram by using the binary expression of an index e. Furthermore, the expression A5 has a function to make the square of itself and increase the index by a multiple number of 2.
In the expressions A1 to A6, since only the product Mont in the Montgomery space is used, attention should be paid to the fact that no division is directly used when encrypting the message M. As described above, the Montgomery method is an effective technique to calculate RSA cryptograph or the like at a high speed.
Description will now be given as to how division is ingeniously avoided in the Montgomery method. In Expression 2 mentioned above, when the numeric values A and B are expressed as binary numbers each of which is formed by k bits and R=2^k is established, the multiplication remainder calculation can be effected by using a shift register or an adder. At this moment, Expression 2 can be expressed as follows.Mont(A·B)=2^−k*{Σ(Aj*B)*2j(j=0, . . . , k−1)}(mod N)  (Expression 4)In Expression 4, although a j-th partial product (Aj*B)*2^j is cumulatively increased in order to calculate the product Mont, a factor 2^−k is realized by using a shifter at this moment.u=0  (B1)for(j=0;j<k;j++){  (B2)u=u+AjB  (B3)if(u0==1)u=u+N  (B4)u=u/2}  (B5)
The above expressions represent a method of calculating Expression 4 by binary addition and shift (which will be referred to as a binary addition shift method hereinafter). This method is based on the fact that the modulus N used in RSA cryptography and the like is usually an odd number. The expression B1 indicates that a provisional value u in the calculation is an initial value 0. The expressions B2 to B5 are for sentences, and a subscript j is incremented by 1 from 0 to k−1 and repeated. The expression B3 indicates that a term Aj*B is nested into the provisional value u, and this corresponds to addition according to each term in Expression 4. The expression B4 determines whether the modulus N is added to the provisional value u. Attention should be paid to the fact that the remainder does not vary even if the modulus N and its multiple number are added to the provisional value u. When u0 which is LSB of the provisional value u is 1, the modulus N is added. Since the modulus N is an odd number, u0 which is LSB of the provisional value u becomes 0 as a result of addition. When u0 which is LSB of the provisional value u is 0, addition of the modulus N is not carried out. As a result, addition according to each term advances while u0 as LSB of the provisional value u is constantly 0 (indicating that u is a multiple number of 2). Although the expression B5 divides the provisional number by 2, this can be realized by one-bit shift since the provisional value u is a multiple number of 2. Incidentally, as to the shift factor 2^−1, the factor becomes 2^−k when calculation of the provisional value u is finished. As described above, in the binary addition shift method, Expression 4 can be obtained by repeating the operation of the expressions B2 to B5.
u0′ (which will be expressed in this way hereinafter) which is LSB of the provisional value u in the expression B4 can be logically obtained before judgment of the expression B4, i.e., the stage of the expression B3.u0′=u0@(AjB0)  (Expression 5)Here, u0 in the right side is a least significant bit of the provisional value u in the expression B3, and B0 is a least significant bit of the numeric value B expressed in the binary notation. Expression 5 means a logical expression to render u0′ (u0 in the expression B4) as LSB of the provisional value u into 0. However, an operator @ means an EOR logic.
As apparent from the above-described calculation, the product Mont in the Montgomery space can be calculated from only addition and shift.
It is to be noted that, as a circuit which executes a calculation based on addition and shift, there is Ser. No. 10/235,541 applied for USPTO on Sep. 6, 2002 by the present applicant.
As described above, the relatively simple processing can suffice because the binary shift addition method renders the least significant bit u0 of the provisional value u into 0, but it is processing for each one bit, which is not efficient.
Thus, as an example to increase the throughput speed by using parallel calculation processing or the like, there is Japanese patent application laid-open No. 7112/2002.
Information processed by, e.g., IC cards or portable terminals is increasing every year, and there is a meaningful demand for reduction in a calculation time with respect to the cipher used in certification or the like. In order to execute the multiplication remainder calculation at a high speed, since the adopting the above-described parallel calculation processing requires a plurality of the same circuits, which results in a large circuit scale.